package interview.demo2.findTree;

import interview.demo2.TreeNode;

/**
 * @author
 * @create 2018-10-13 11:04
 **/
public class Test {


    public static void main(String[] args) {
        int[] arrays = {2, 3, 1, 4, 5};

        TreeRoot treeRoot = new TreeRoot();
        for (int a : arrays) {
            createTree(treeRoot, a);
        }
        //   2
        // 1    3
        //        4
        //          5

        //先序遍历： 2  1 3 4 5
        preTraverseTree(treeRoot.getTreeRoot());

    }

    /**
     * 动态创建二叉查找树
     *
     * @param treeRoot 根节点
     * @param value    节点的值
     */
    public static void createTree(TreeRoot treeRoot, int value) {


        //如果树根为空(第一次访问)，将第一个值作为根节点
        if (treeRoot.getTreeRoot() == null) {
            TreeNode treeNode = new TreeNode(value);
            treeRoot.setTreeRoot(treeNode);

        } else {

            //当前树根
            TreeNode tempRoot = treeRoot.getTreeRoot();

            //这里是个循环，就是通过不断判断节点是否为空，然后再判断节点值大小来对节点进行创建
            while (tempRoot != null) {
                //当前值大于根值，往右边走
                if (value > tempRoot.getValue()) {

                    //右边没有树根，那就直接插入
                    if (tempRoot.getRightNode() == null) {
                        tempRoot.setRightNode(new TreeNode(value));
                        return;
                    } else {
                        //如果右边有树根，到右边的树根去
                        tempRoot = tempRoot.getRightNode();
                    }
                } else {
                    //左没有树根，那就直接插入
                    if (tempRoot.getLeftNode() == null) {
                        tempRoot.setLeftNode(new TreeNode(value));

                        return;
                    } else {
                        //如果左有树根，到左边的树根去
                        tempRoot = tempRoot.getLeftNode();
                    }
                }
            }
        }
    }

    public static void createTree2(TreeRoot treeRoot, int value) {
        //判断当前根节点有没有值，没有则去创建作为根节点
        //否则，设置temp为当前节点，进行循环，通过判断该值比当前节点大还是当前节点小
        if (treeRoot.getTreeRoot() == null) {
            treeRoot.setTreeRoot(new TreeNode(value));
        } else {
            TreeNode tempRoot = treeRoot.getTreeRoot();
            while (tempRoot != null) {
                //判断当前值是否小于根节点
                if (value < tempRoot.getValue()) {
                    //如果左边节点为空，则直接插入
                    if (tempRoot.getLeftNode() == null) {
                        tempRoot.setLeftNode(new TreeNode(value));
                    } else {
                        tempRoot = tempRoot.getLeftNode();
                    }
                } else {
                    if (tempRoot.getRightNode() == null) {
                        tempRoot.setRightNode(new TreeNode(value));
                    } else {
                        tempRoot = tempRoot.getRightNode();
                    }
                }
            }
        }
    }

    /**
     * 先序遍历
     *
     * @param rootNode
     */
    public static void preTraverseTree(TreeNode rootNode) {
        if (rootNode != null) {
            //访问根节点
            System.out.print(rootNode.getValue() + " ");
            //访问左节点
            preTraverseTree(rootNode.getLeftNode());
            //访问右节点
            preTraverseTree(rootNode.getRightNode());

        }
    }

}
